package algorithm;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author MaGuangQi
 * @description: 用队列实现栈 225题
 * https://leetcode-cn.com/problems/implement-stack-using-queues/
 * @date 2020-06-15 19:04
 **/
public class QueueGenStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;
    Integer tail = 0;

    public QueueGenStack() {
        q1 = new ArrayDeque<Integer>();
        q2 = new ArrayDeque<Integer>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        q1.add(x);
        tail = x;
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        if (q1.isEmpty()) {
            throw new RuntimeException("没有元素");
        }
        while (q1.size() > 1) {
            //将队列q1的元素出队,然后移动到q2的队列
            //将倒数第2个元素作为栈顶元素保存,作为下一次调用top方法时返回.因为最后一个元素
            //在此方法要被弹出了.
            tail=q1.remove();
            q2.add(tail);
        }

        //不能使用for循环,因为q1.remove后,q1.size变了.
       /* for (int i = 0; i < q1.size() - 1; i++) {
            //将队列q1的元素出队,然后移动到q2的队列
            //将倒数第2个元素作为栈顶元素保存,作为下一次调用top方法时返回.因为最后一个元素
            //在此方法要被弹出了.
            tail=q1.remove();
            q2.add(tail);
        }*/
        //此时q1队列还剩余一个元素,这个元素是栈顶元素
        int last=q1.remove();
        //此时q1为空了,q2中保存着剩下的元素
        //此处有坑,不能直接q1=q2,因为这样q2中仍然有元素,下次再调用的时候,q2中的元素就重复了.
        // 所以需要每次把q2清空,然后每次调用pop时,q2只有q1剩余的元素.恰好每次q1是空的
        //所以q1和q2交换即可
        Queue<Integer> tmp=q1;
        q1=q2;
        q2=tmp;
        return last;

    }

    /**
     * Get the top element.
     */
    public int top() {
        if (q1.isEmpty()) {
            throw new RuntimeException("没有元素");
        }
        return tail;
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return q1.isEmpty();
    }

    public static void main(String[] args) {
        QueueGenStack stack = new QueueGenStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("栈顶"+stack.top());
        System.out.println(stack.pop());
        System.out.println("栈顶"+stack.top());
        System.out.println(stack.pop());
        System.out.println("栈顶"+stack.top());
        System.out.println(stack.pop());
    }
}
